#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    struct Status
    {
        unsigned long L;
        unsigned long R;
    };
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tmp = nums1.size() + nums2.size();
        if (tmp % 2 == 0)    return double(solve(nums1, { 0,nums1.size()},
            nums2, { 0,nums2.size()},
            tmp / 2)
            +
            solve(nums1, { 0,nums1.size()},
                nums2, { 0,nums2.size()},
                tmp / 2 + 1)
            ) / 2.0;
        else                return double(solve(nums1, { 0,nums1.size()},
            nums2, { 0,nums2.size()},
            tmp / 2 + 1)
            );
    }
    int solve(vector<int>& nums1, Status s1, vector<int>& nums2, Status s2, int k) {
        if (s1.R == 0) return nums2[k - 1];
        if (s2.R == 0) return nums1[k - 1];
        if (s1.L == s1.R) return nums2[s2.L + k - 1];
        if (s2.L == s2.R) return nums1[s1.L + k - 1];
        if (k == 1) return min(nums1[s1.L], nums2[s2.L]);

        int mid = k / 2;
        unsigned long index1 = min(s1.R, s1.L + mid) - 1;
        unsigned long index2 = min(s2.R, s2.L + mid) - 1;

        if (nums1[index1] <= nums2[index2]) {
            return solve(nums1, { index1 + 1,s1.R },
                nums2, s2,
                k - (index1 - s1.L + 1));
        }
        else {
            return solve(nums1, s1,
                nums2, { index2 + 1,s2.R },
                k - (index2 - s2.L + 1));
        }
    }
};

int main()
{
    vector<int> A{ 1,3 };
    vector<int> B{ 2,4 };
    Solution S;
    cout << fixed << S.findMedianSortedArrays(A, B) << endl;
    return 0;
}